//完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大，第 n 层有 2ⁿ⁻¹ 个节点）的，并且所有的节点都尽可能地集中在左侧。 
//
// 设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作： 
//
// 
// CBTInserter(TreeNode root) 使用根节点为 root 的给定树初始化该数据结构； 
// CBTInserter.insert(int v) 向树中插入一个新节点，节点类型为 TreeNode，值为 v 。使树保持完全二叉树的状态，并返回插入的
//新节点的父节点的值； 
// CBTInserter.get_root() 将返回树的根节点。 
// 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 
//输入：inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]]
//输出：[null,1,[1,2]]
// 
//
// 示例 2： 
//
// 
//输入：inputs = ["CBTInserter","insert","insert","get_root"], inputs = [[[1,2,3,4,
//5,6]],[7],[8],[]]
//输出：[null,3,4,[1,2,3,4,5,6,7,8]]
// 
//
// 
//
// 提示： 
//
// 
// 最初给定的树是完全二叉树，且包含 1 到 1000 个节点。 
// 每个测试用例最多调用 CBTInserter.insert 操作 10000 次。 
// 给定节点或插入节点的每个值都在 0 到 5000 之间。 
// 
//
// 
//
// 
// 注意：本题与主站 919 题相同： https://leetcode-cn.com/problems/complete-binary-tree-
//inserter/ 
//
// Related Topics 树 广度优先搜索 设计 二叉树 👍 66 👎 0


package LeetCode.editor.cn;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;

/**
 * @author ldltd
 * @date 2025-02-13 22:34:59
 * @description LCR 043.完全二叉树插入器
 */
public class NaqhDT{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 NaqhDT fun=new NaqhDT();


	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

 // Definition for a binary tree node.
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
class CBTInserter1 {
         TreeNode p=new TreeNode(-1);
         Deque<TreeNode> q=new ArrayDeque<>();
    public CBTInserter1(TreeNode root) {
        p.left=root;
        q.offer(root);
        while (!q.isEmpty()){
            if(q.peek().right==null) {
                if(q.peek().left!=null) q.offer(q.peek().left);
                break;
            }
            root=q.poll();
            q.offer(root.left);
            q.offer(root.right);
        }
    }
    
    public int insert(int v) {
        TreeNode node = new TreeNode(v);
        if(q.peek().left==null) {
            q.peek().left= node;
            q.offer(node);
            return q.peek().val;
        }
            q.peek().right= node;
            q.offer(node);
        return   q.poll().val;
    }
    
    public TreeNode get_root() {
        return p.left;
    }
}

/*那么我们可以发现，按照广度优先搜索的顺序，完全二叉树中的所有节点的编号是连续的。这可以用二进制表示看出：完全二叉树的第 i(i≥1) 层有 2
i−1
  个节点，它们的编号恰好对应着 i 位的二进制表示，共有 2
i−1
  个（最高位必须为 1）。当某个节点编号为 x 时，左子节点的编号 2x 即为将 x 的二进制表示左移一位后在最低位补 0，右子节点的编号即为将 x 的二进制表示左移一位后在最低位补 1。

因此，在初始化时，我们只需要使用深度优先搜索或者广度优先搜索，得到初始完全二叉树中的节点个数。在调用 insert(v) 时，我们可以知道它的编号 x，那么就可以从高到低遍历 x 的每一个二进制位（忽略最高位的 1），如果为 0 就往左子节点移动，否则往右子节点移动，这样就可以到达节点需要被插入的位置。

*/
class CBTInserter {
    int cnt;
    TreeNode root;

    public CBTInserter(TreeNode root) {
        this.cnt = 0;
        this.root = root;

        Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            ++cnt;
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    public int insert(int val) {
        ++cnt;
        TreeNode child = new TreeNode(val);
        TreeNode node = root;
        //返回无符号整型 i 的最高非零位前面的 0 的个数。
        int highbit = 31 - Integer.numberOfLeadingZeros(cnt);
        for (int i = highbit - 1; i >= 1; --i) {
            if ((cnt & (1 << i)) != 0) {
                node = node.right;
            } else {
                node = node.left;
            }
        }
        if ((cnt & 1) != 0) {
            node.right = child;
        } else {
            node.left = child;
        }
        return node.val;
    }

    public TreeNode get_root() {
        return root;
    }
}

/**
 * Your CBTInserter object will be instantiated and called as such:
 * CBTInserter obj = new CBTInserter(root);
 * int param_1 = obj.insert(v);
 * TreeNode param_2 = obj.get_root();
 */
//leetcode submit region end(Prohibit modification and deletion)

}
